package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/8/16 19:36
 */
public class _278_第一个错误的版本 {

    private final static Integer BAD_V = 1702766719;

    public static void main(String[] args) {
        int n = 2126753390;
        System.err.println(firstBadVersion(n));

    }

    public static int firstBadVersion(int n) {
        int lp = 1;
        int rp = n;
        while (lp < rp) {
            int m = lp + (rp - lp) / 2;
            if (isBadVersion(m)){
                //如果该版本错误，我们向前回溯。那如果此m版本恰好是所求呢？m - 1 就跳过了？
                rp = m - 1;
            }else{
                //如果该版本无误，向右查找
                lp = m + 1;
            }
        }
        //解决rp = m - 1的问题，如果最终lp版本不是错误版本，那么它的下一版本一定是错误版本
        return isBadVersion(lp) ? lp : lp +1;
    }

    public static boolean isBadVersion(int m) {
        return m >= BAD_V;
    }
}
